{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Index Sum of Two Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findRestaurant"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个列表的最小索引总和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。</p>\n",
    "\n",
    "<p>你需要帮助他们用<strong>最少的索引和</strong>找出他们<strong>共同喜爱的餐厅</strong>。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>list1 = [\"Shogun\", \"Tapioca Express\", \"Burger King\", \"KFC\"]，list2 = [\"Piatti\", \"The Grill at Torrey Pines\", \"Hungry Hunter Steakhouse\", \"Shogun\"]\n",
    "<strong>输出:</strong> [\"Shogun\"]\n",
    "<strong>解释:</strong> 他们唯一共同喜爱的餐厅是“Shogun”。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>list1 = [\"Shogun\", \"Tapioca Express\", \"Burger King\", \"KFC\"]，list2 = [\"KFC\", \"Shogun\", \"Burger King\"]\n",
    "<strong>输出:</strong> [\"Shogun\"]\n",
    "<strong>解释:</strong> 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= list1.length, list2.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= list1[i].length, list2[i].length &lt;= 30</code>&nbsp;</li>\n",
    "\t<li><code>list1[i]</code> 和 <code>list2[i]</code> 由空格<meta charset=\"UTF-8\" />&nbsp;<code>' '</code>&nbsp;和英文字母组成。</li>\n",
    "\t<li><code>list1</code> 的所有字符串都是 <strong>唯一</strong> 的。</li>\n",
    "\t<li><code>list2</code> 中的所有字符串都是 <strong>唯一</strong> 的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-index-sum-of-two-lists](https://leetcode.cn/problems/minimum-index-sum-of-two-lists/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-index-sum-of-two-lists](https://leetcode.cn/problems/minimum-index-sum-of-two-lists/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"Shogun\",\"Tapioca Express\",\"Burger King\",\"KFC\"]\\n[\"Piatti\",\"The Grill at Torrey Pines\",\"Hungry Hunter Steakhouse\",\"Shogun\"]', '[\"Shogun\",\"Tapioca Express\",\"Burger King\",\"KFC\"]\\n[\"KFC\",\"Shogun\",\"Burger King\"]', '[\"happy\",\"sad\",\"good\"]\\n[\"sad\",\"happy\",\"good\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1, list2):\n",
    "        \"\"\"\n",
    "        :type list1: List[str]\n",
    "        :type list2: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        N= len(list1)\n",
    "        M = len(list2)\n",
    "        lookup = {list1[i]:i for i in range(N)}\n",
    "        ans = []\n",
    "        import sys\n",
    "        min_sum = sys.maxsize\n",
    "        for i in range(M):\n",
    "            if list2[i] in lookup.keys():\n",
    "                if lookup.get(list2[i]) +i <min_sum:\n",
    "                    min_sum=i+lookup[list2[i]]\n",
    "                    ans.clear()\n",
    "                    ans.append(list2[i])\n",
    "                elif lookup.get(list2[i]) +i ==min_sum:\n",
    "                    ans.append(list2[i])\n",
    "        return ans\n",
    "            \n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1, list2):\n",
    "        \"\"\"\n",
    "        :type list1: List[str]\n",
    "        :type list2: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        d = {v: i for i, v in enumerate(list1)}\n",
    "        d2 = {}\n",
    "        for i, v in enumerate(list2):\n",
    "            if v in d:\n",
    "                d2[v] = i + d[v]\n",
    "        minv = min(d2.values())\n",
    "        return [k for k, v in d2.items() if v == minv]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1, list2):\n",
    "        \"\"\"\n",
    "        :type list1: List[str]\n",
    "        :type list2: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        cmn_rst = set(list1) & set(list2)\n",
    "        dic1 = {k:i for i,k in enumerate(list1) if k in cmn_rst}\n",
    "        dic2 = {k:i for i,k in enumerate(list2) if k in cmn_rst}\n",
    "        min_cmn_index = len(list1) + len(list2)\n",
    "        res = []\n",
    "        for rst in cmn_rst:\n",
    "            tmp_index = dic1[rst] + dic2[rst]\n",
    "            if tmp_index < min_cmn_index:\n",
    "                res = [rst]\n",
    "                min_cmn_index = tmp_index\n",
    "            elif tmp_index == min_cmn_index:\n",
    "                res.append(rst)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1, list2):\n",
    "        \"\"\"\n",
    "        :type list1: List[str]\n",
    "        :type list2: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        dct1 = dict([(i[1],i[0]) for i in enumerate(list1)])\n",
    "        dct2 = dict([(i[1],i[0]) for i in enumerate(list2)])\n",
    "        st = set(dct1.keys())&set(dct2.keys())\n",
    "        dct = {}\n",
    "        for i in st:\n",
    "            dct[i] = dct1[i]+dct2[i]\n",
    "        lst = list(dct.items())\n",
    "        lst.sort(key=lambda x: x[1])\n",
    "        res = [i[0] for i in lst if i[1]==lst[0][1]]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1, list2):\n",
    "        \"\"\"\n",
    "        :type list1: List[str]\n",
    "        :type list2: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        d1 = {}\n",
    "        for i, k in enumerate(list1):\n",
    "            d1[k] = i\n",
    "        d2 = {}\n",
    "        for i, k in enumerate(list2):\n",
    "            d2[k] = i\n",
    "            \n",
    "        s = []\n",
    "        for x in range((len(list1) + len(list2))):\n",
    "            s.append([])\n",
    "        for k in d1:\n",
    "            if k in d2:\n",
    "                s[d1[k] + d2[k]].append(k)\n",
    "        for x in s:\n",
    "            if x:\n",
    "                return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1, list2):\n",
    "        \"\"\"\n",
    "        :type list1: List[str]\n",
    "        :type list2: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        min=2**32\n",
    "        res=[]\n",
    "        d1=dict([(list1[i],i) \\\n",
    "                 for i in range(len(list1))])\n",
    "        d2=dict([list2[i],i] \\\n",
    "               for i in range(len(list2)))\n",
    "        for k in d1:\n",
    "            temp=d2.get(k,2**32)\n",
    "            if d1[k]+temp<min:\n",
    "                res=[]\n",
    "                min=d1[k]+temp\n",
    "                res.append(k)\n",
    "            elif d1[k]+temp==min:\n",
    "                res.append(k)\n",
    "            else:\n",
    "                continue\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findRestaurant(self, list1, list2):\n",
    "\n",
    "        cache = dict()\n",
    "        for index, value in enumerate(list1):\n",
    "            cache.setdefault(value, index)\n",
    "        minValue = len(list1) + len(list2)\n",
    "        res = []\n",
    "        for index, value in enumerate(list2):\n",
    "            if cache.get(value) is not None:   # 索引为0\n",
    "                index1 = cache.get(value)\n",
    "                if index + index1 == minValue:\n",
    "                    res.append(value)\n",
    "                elif index1 + index < minValue:\n",
    "                    minValue = index + index1\n",
    "                    res.clear()\n",
    "\n",
    "                    res.append(value)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "\n",
    "        dic={}\n",
    "        for i in range(len(list1)):\n",
    "            dic[list1[i]]=i\n",
    "\n",
    "        res=[]\n",
    "        tmp=float('inf')\n",
    "\n",
    "        for i in range(len(list2)):\n",
    "            if list2[i] not in dic:\n",
    "                continue\n",
    "                \n",
    "            if i+dic[list2[i]]<tmp:\n",
    "                res=[]\n",
    "                tmp=i+dic[list2[i]]\n",
    "                res=[list2[i]]\n",
    "            elif i+dic[list2[i]]==tmp:\n",
    "                res.append(list2[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        arr={key1:value1 for value1,key1 in enumerate(list1)}\n",
    "        res={key2:value2 for value2,key2 in enumerate(list2)}\n",
    "        zong={}\n",
    "        for i in arr:\n",
    "            if i in res:\n",
    "                zong[i]=res[i]+arr[i]\n",
    "        a,ans=min(zong.values()),[]\n",
    "        for i in zong:\n",
    "            if zong[i]==a:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        common=set(list1)&set(list2)\n",
    "        d1={}\n",
    "        d2={}\n",
    "        for i in range(len(list1)):\n",
    "            d1[list1[i]]=i\n",
    "        for i in range(len(list2)):\n",
    "            d2[list2[i]]=i\n",
    "        m=min([d1[c]+d2[c] for c in common])\n",
    "        return [c for c in common if m==d1[c]+d2[c]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        dict={}\n",
    "        for i in range(len(list1)):\n",
    "            dict[list1[i]]=i\n",
    "        c=[]\n",
    "        for i in range(len(list2)):\n",
    "            if list2[i] in dict:\n",
    "                dict[list2[i]]+=i\n",
    "                c.append([dict[list2[i]],list2[i]])\n",
    "        c.sort()\n",
    "        a=c[0][0]\n",
    "        num=1\n",
    "        for i in range(len(c)):\n",
    "            b=c[i][0]\n",
    "            if b==a:\n",
    "                num+=1\n",
    "            else:\n",
    "                break\n",
    "        d=[]\n",
    "        for i in range(num-1):\n",
    "            d.append(c[i][1])\n",
    "        return d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        S = set(list1) & set(list2)\n",
    "        d = {s:0 for s in S}\n",
    "        for i, x in enumerate(list1):\n",
    "            if x in d:\n",
    "                d[x] = i\n",
    "        for j, y in enumerate(list2):\n",
    "            if y in d:\n",
    "                d[y] +=j\n",
    "\n",
    "        M = min(d.values())\n",
    "\n",
    "        return [k for k, v in d.items() if v == M]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        d = {}\n",
    "        name = []\n",
    "        small_idx = 2**31-1\n",
    "\n",
    "        for i in range(len(list1)):\n",
    "            d[list1[i]] = [i]\n",
    "        \n",
    "        for i in range(len(list2)):\n",
    "            k = list2[i]\n",
    "            if k in d:\n",
    "                d[k].append(i)\n",
    "                if sum(d[k]) < small_idx:\n",
    "                    small_idx = sum(d[k])\n",
    "                    name = [k]\n",
    "                elif sum(d[k]) == small_idx:\n",
    "                    name.append(k)\n",
    "        return name"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        restaurantDict = collections.defaultdict(list)\n",
    "        for i in range(len(list1)):\n",
    "            restaurantDict[list1[i]].append(i)\n",
    "        for i in range(len(list2)):\n",
    "            restaurantDict[list2[i]].append(i)\n",
    "        resDict = collections.defaultdict(int)\n",
    "        for key in restaurantDict:\n",
    "            if len(restaurantDict[key]) == 2:\n",
    "                resDict[key] = sum(restaurantDict[key])\n",
    "        res = []\n",
    "        minIndex = min(resDict.values())\n",
    "        for key in resDict:\n",
    "            if resDict[key] == minIndex:\n",
    "                res.append(key)\n",
    "        return res \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        di={}\n",
    "        for index,value in enumerate(list1):\n",
    "            di.setdefault(value,[])\n",
    "            di[value].append(index)\n",
    "        for index,value in enumerate(list2):\n",
    "            di.setdefault(value,[])\n",
    "            di[value].append(index)\n",
    "        re = None\n",
    "        li=[]\n",
    "        for key,value in di.items():\n",
    "            if len(value) ==1:\n",
    "                continue\n",
    "            if re is None:\n",
    "                re = sum(value)\n",
    "                li.append(key)\n",
    "            elif sum(value) <re:\n",
    "                re= sum(value)\n",
    "                del li[:]\n",
    "                li.append(key)\n",
    "            elif sum(value)==re:\n",
    "                li.append(key)\n",
    "        return li\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        d = {}\n",
    "        for i in range(len(list1)):\n",
    "            d[list1[i]] = [i]\n",
    "        \n",
    "        for i in range(len(list2)):\n",
    "            if list2[i] in d:\n",
    "                d[list2[i]].append(i)\n",
    "        print(d)\n",
    "\n",
    "        name = []\n",
    "        small_idx = 2**31-1\n",
    "        for k in d.keys():\n",
    "            if len(d[k]) == 2:\n",
    "                print(k, sum(d[k]))\n",
    "                if sum(d[k]) < small_idx:\n",
    "                    small_idx = sum(d[k])\n",
    "                    name = [k]\n",
    "                elif sum(d[k]) == small_idx:\n",
    "                    name.append(k)\n",
    "        return name\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.com/contest/leetcode-weekly-contest-34/problems/minimum-index-sum-of-two-lists/\n",
    "import os, sys, shutil, glob, re\n",
    "import time, calendar\n",
    "from datetime import datetime, timezone\n",
    "import hashlib, zipfile, zlib\n",
    "from math import *\n",
    "from operator import itemgetter\n",
    "from functools import wraps, cmp_to_key, reduce, lru_cache\n",
    "from itertools import count, combinations, permutations\n",
    "from collections import namedtuple, defaultdict, Counter, deque\n",
    "from queue import Queue\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "  def findRestaurant(self, list1, list2): # -> List[str]\n",
    "    choices = [(i+j,r1) for i, r1 in enumerate(list1) for j, r2 in enumerate(list2) if r1==r2]\n",
    "    minIndexSum = min(choices)[0]\n",
    "    return list(map(itemgetter(1), filter(lambda c: c[0] == minIndexSum, choices)))\n",
    "\n",
    "\n",
    "\n",
    "if __name__ == '__main__' and ('SJDEAK' in os.environ):\n",
    "  from utils.tree import TreeNode, array2TreeNode\n",
    "\n",
    "  def test(*args):\n",
    "    print('输入数据: ', *args)\n",
    "    print('结果: ', Solution().findRestaurant(*args), end='\\n-----\\n')\n",
    "\n",
    "\n",
    "  test([\"Shogun\", \"Tapioca Express\", \"Burger King\", \"KFC\"],[\"Piatti\", \"The Grill at Torrey Pines\", \"Hungry Hunter Steakhouse\", \"Shogun\"])\n",
    "  test([\"Shogun\", \"Tapioca Express\", \"Burger King\", \"KFC\"], [\"KFC\", \"Shogun\", \"Burger King\"])\n",
    "else:\n",
    "  print = lambda *args, **kwargs: None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        '''\n",
    "        '''\n",
    "        res = defaultdict(list)\n",
    "        for i,l1 in enumerate(list1):\n",
    "            for j,l2 in enumerate(list2):\n",
    "                if l1 == l2:\n",
    "                    res[i+j].append(l1)\n",
    "                    break\n",
    "        \n",
    "        return res[min(res.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        s=set(list1)\n",
    "        resdic=defaultdict(list)\n",
    "        for i in range(len(list2)):\n",
    "            if list2[i] in s:\n",
    "                if i+list1.index(list2[i]) in resdic.keys():\n",
    "                    resdic[i+list1.index(list2[i])].append(list2[i])\n",
    "                else:\n",
    "                    resdic[i+list1.index(list2[i])]=[list2[i]]\n",
    "        return resdic[min(resdic.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        # res_idx = []\n",
    "        # for i in range(len(list1)):\n",
    "        #     if list1[i] in list2:\n",
    "        #         idx = list2.index(list1[i])\n",
    "        #         res_idx.append([i,idx])\n",
    "        # res_idx = sorted(res_idx, key = lambda v:v[0]+v[1])\n",
    "        # res = [list1[res_idx[0][0]]]\n",
    "        # sum = res_idx[0][0]+res_idx[0][1]\n",
    "        # for i in range(1, len(res_idx)):\n",
    "        #     if res_idx[i][0]+res_idx[i][1]==sum:\n",
    "        #         res.append(list1[res_idx[i][0]])\n",
    "        # return res\n",
    "\n",
    "        # idea2\n",
    "        # agreement = set(list1) &set(list2)\n",
    "        # res_idx = []\n",
    "        # for value in agreement:\n",
    "        #     idx1 = list1.index(value)\n",
    "        #     idx2 = list2.index(value)\n",
    "        #     res_idx.append((idx1,idx2))\n",
    "        # res_idx = sorted(res_idx, key = lambda v:v[0]+v[1])\n",
    "        # res = [list1[res_idx[0][0]]]\n",
    "        # sum = res_idx[0][0]+res_idx[0][1]\n",
    "        # for i in range(1, len(res_idx)):\n",
    "        #     if res_idx[i][0]+res_idx[i][1]==sum:\n",
    "        #         res.append(list1[res_idx[i][0]])\n",
    "        # return res\n",
    "        index1 = {list1[i]: i for i in range(len(list1))}\n",
    "        index2 = {list2[i]: i for i in range(len(list2))}\n",
    "        agreements = set(list1) & set(list2)\n",
    "        sum_index = {r: index1[r]+index2[r] for r in agreements}\n",
    "        return [r for r in agreements if sum_index[r] == min(sum_index.values())]\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        # res_idx = []\n",
    "        # for i in range(len(list1)):\n",
    "        #     if list1[i] in list2:\n",
    "        #         idx = list2.index(list1[i])\n",
    "        #         res_idx.append([i,idx])\n",
    "        # res_idx = sorted(res_idx, key = lambda v:v[0]+v[1])\n",
    "        # res = [list1[res_idx[0][0]]]\n",
    "        # sum = res_idx[0][0]+res_idx[0][1]\n",
    "        # for i in range(1, len(res_idx)):\n",
    "        #     if res_idx[i][0]+res_idx[i][1]==sum:\n",
    "        #         res.append(list1[res_idx[i][0]])\n",
    "        # return res\n",
    "\n",
    "        # idea2\n",
    "        # agreement = set(list1) &set(list2)\n",
    "        # res_idx = []\n",
    "        # for value in agreement:\n",
    "        #     idx1 = list1.index(value)\n",
    "        #     idx2 = list2.index(value)\n",
    "        #     res_idx.append((idx1,idx2))\n",
    "        # res_idx = sorted(res_idx, key = lambda v:v[0]+v[1])\n",
    "        # res = [list1[res_idx[0][0]]]\n",
    "        # sum = res_idx[0][0]+res_idx[0][1]\n",
    "        # for i in range(1, len(res_idx)):\n",
    "        #     if res_idx[i][0]+res_idx[i][1]==sum:\n",
    "        #         res.append(list1[res_idx[i][0]])\n",
    "        # return res\n",
    "        index1 = {list1[i]: i for i in range(len(list1))}\n",
    "        index2 = {list2[i]: i for i in range(len(list2))}\n",
    "        agreements = set(list1) & set(list2)\n",
    "        sum_index = {r: index1[r]+index2[r] for r in agreements}\n",
    "        return [r for r in agreements if sum_index[r] == min(sum_index.values())]\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        mp = collections.defaultdict(lambda:[-1,-1])\n",
    "        for i,l in enumerate(list1):\n",
    "            mp[l][0] = i\n",
    "        for i,l in enumerate(list2):\n",
    "            mp[l][1] = i\n",
    "        ll = [i for i in list(mp.items()) if i[1][0] != -1 and i[1][1] != -1]\n",
    "        ll.sort(key=lambda x:(x[1][0]+x[1][1]))\n",
    "        ans = []\n",
    "        for l in ll:\n",
    "            if l[1][0] + l[1][1] == ll[0][1][0] + ll[0][1][1]:\n",
    "                ans.append(l[0])\n",
    "            else:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        hash_map = {}\n",
    "        for i, e in enumerate(list1):\n",
    "            if e not in hash_map:\n",
    "                hash_map[e] = {\"count\": 1, \"indices\":[i]}\n",
    "            else:\n",
    "                hash_map[e][\"count\"] += 1\n",
    "                hash_map[e][\"indices\"].append(i)\n",
    "        for i, e in enumerate(list2):\n",
    "            if e not in hash_map:\n",
    "                hash_map[e] = {\"count\": 1, \"indices\":[i]}\n",
    "            else:\n",
    "                hash_map[e][\"count\"] += 1\n",
    "                hash_map[e][\"indices\"].append(i)\n",
    "        result = {k: sum(hash_map[k][\"indices\"]) for k in hash_map if hash_map[k][\"count\"] == 2}\n",
    "        m = min(result.values())\n",
    "        return [k for k in result if result[k] == m]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        min_index = -1\n",
    "        result = {}\n",
    "        for index1,res1 in enumerate(list1):\n",
    "            for index2,res2 in enumerate(list2):\n",
    "                if res1 == res2:\n",
    "                    min_index = min(min_index,index1 + index2)\n",
    "                    result[res1] = index1 + index2\n",
    "        soeted_re = dict(sorted(result.items(),key=lambda x:x[1]))\n",
    "        retu = []\n",
    "        for res,index in soeted_re.items():\n",
    "            if index == min(soeted_re.values()):\n",
    "                retu.append(res)\n",
    "        return retu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "        iss=[0]*len(list1)\n",
    "        for i in range(len(list1)):\n",
    "            if list1[i] in list2:\n",
    "                iss[i]=i+list2.index(list1[i])\n",
    "            else:\n",
    "                iss[i]=2000\n",
    "        m=min(iss)\n",
    "        ret=[]\n",
    "        for i in range(len(list1)):\n",
    "            if iss[i]==m:\n",
    "                ret.append(list1[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:\n",
    "      index=[]\n",
    "      restaurant=[]\n",
    "      for i in range(len(list1)):\n",
    "          if(list1[i] in list2):\n",
    "              restaurant.append(list1[i])\n",
    "              index.append(i+list2.index(restaurant[-1]))\n",
    "      #print(restaurant,index)\n",
    "      finallist =[]\n",
    "      #finallist.append(restaurant[index.index(min(index))])\n",
    "      min_indices = [i for i, score in enumerate(index) if score == min(index)]\n",
    "      for i in range(len(min_indices)):\n",
    "        finallist.append(restaurant[min_indices[i]])\n",
    "      return finallist"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
